package dataStructure

import (
	"bytes"
	"math"
	"math/rand"
	"sync"
	"time"
)

const (
	//跳表索引最大层数，可根据实际情况进行调整
	maxLevel    int     = 18
	probability float64 = 1 / math.E
)

// https://www.jianshu.com/p/6a8d1f88f246
// elementNode 数组指针，指向元素
type elementNode struct {
	next []*Element
}

// Element 跳转表数据结构
type Element struct {
	elementNode
	key   []byte      // 用以排序和判断大小的关键字
	value interface{} // 定义元素，附加
}

func (element *Element) ElementGetValue() interface{} {
	return element.value
}

// 得到某个element的value
func (element *Element) Value() interface{}  {
	return element.value
}


type SkipList struct {
	elementNode
	maxLevel       int            // 最大深度
	length         int            // 长度,跳表中
	randSource     rand.Source    // 动态调节跳转表的长度
	probability    float64        // 概率
	probTable      []float64      // 存储位置，对应key
	mutex          sync.RWMutex   // 保证线程安全
	prevNodesCache []*elementNode // 缓存
}

// NewSkipList 初始化一个空的跳表
func NewSkipList() *SkipList {
	return &SkipList{
		elementNode:    elementNode{next: make([]*Element, maxLevel)},
		prevNodesCache: make([]*elementNode, maxLevel),
		maxLevel:       maxLevel,
		randSource:     rand.New(rand.NewSource(time.Now().UnixNano())),
		probability:    probability,
		probTable:      probabilityTable(probability, maxLevel),
	}
}

func probabilityTable(probability float64, maxLevel int) (table []float64) {
	for i := 1; i <= maxLevel; i++ {
		prob := math.Pow(probability, float64(i-1))
		table = append(table, prob)
	}
	return table
}

// 找到前一个节点
func (skiplist *SkipList) getPrevElementNodes(key []byte) []*elementNode {
	var prev = &skiplist.elementNode // 保存前置结点
	var next *Element
	prevs := skiplist.prevNodesCache // 缓冲集合
	for i := skiplist.maxLevel - 1; i >= 0; i-- {
		next = prev.next[i] // 循环跳到下一个
		for next != nil && bytes.Compare(key, next.key) > 0 {
			prev = &next.elementNode
			next = next.next[i]
		}
		prevs[i] = prev
	}
	return prevs
}

// Put方法，将一个key和value插入跳表中 不支持相同的key
func (skiplist *SkipList) Put(key []byte, value interface{}) *Element {
	skiplist.mutex.Lock()
	defer skiplist.mutex.Unlock() // 线程安全

	var element *Element
	prevs := skiplist.getPrevElementNodes(key)
	if element = prevs[0].next[0]; element != nil && bytes.Compare(element.key, key) <= 0 {
		element.value = value
		return element
	}

	element = &Element{
		// 通过概率随机指定一个 level 给新插入的元素，调用了前面出现的函数 randLevel
		elementNode: elementNode{next: make([]*Element, skiplist.randLevel())},
		key:         key,
		value:       value,
	}
	skiplist.length++

	for i := range element.next { // 插入数据
		element.next[i] = prevs[i].next[i]
		prevs[i].next[i] = element // 记录位置
	}

	return element
}

// 随机计算最接近的
func (skiplist *SkipList) randLevel() (level int) {
	r := float64(skiplist.randSource.Int63()) / (1 << 63)
	level = 1
	for level < skiplist.maxLevel && r < skiplist.probTable[level] {
		level++ // 级别追加
	}

	return level
}

// 通过key找到node
func (skiplist *SkipList) Get(key []byte) *Element {
	var prev = &skiplist.elementNode
	var next *Element

	for i := skiplist.maxLevel - 1; i >= 0; i-- {
		next = prev.next[i]

		for next != nil && bytes.Compare(key, next.key) > 0 {
			prev = &next.elementNode
			next = next.next[i]
		}
	}

	if next != nil && bytes.Compare(next.key, key) <= 0 {
		return next
	}

	return nil
}

// 检测是否存在某个key
func (skiplist *SkipList) Exist(key []byte) bool {
	return skiplist.Get(key) != nil
}


